In this paper, we present a fully-dynamic distributed algorithm formaintaining a minimum spanning tree on general graphs with positive real edgeweights. The goal of a dynamic MST algorithm is to update efficiently theminimum spanning tree after dynamic changes like edge weight changes, ratherthan having to recompute it from scatch each time. The first part of the papersurveys various algorithms available today both in sequential and distributedenvironments to solve static MST problem. We also present some of the efficientsequential algorithms for computing dynamic MST like the Frederickson'salgorithm and Eppstein's sparsification technique. Lastly we present our newsequential and distributed algorithms for dynamic MST problem. To ourknowledge, this is the first of the distributed algorithms for computingdynamic MSTs.
展开▼
